package history.study.dynamic_programming;

// 198. 打家劫舍

/**
 *  1. dp[i] 表示有i户人家时，可以盗取得最多金额
 *  2. dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i])
 *  3. dp[0] = nums[0];
 *     dp[1] = Math.max(nums[0], nums[1]);
 *  4. 从前往后遍历
 *  5. dp[2] = Math.max(dp[1], dp[0]+nums[2])
 */
public class LeetCode_198 {
    public int rob(int[] nums) {
        int length = nums.length;
        if (length == 0) return 0;
        if (length == 1) return nums[0];
        int []state = new int[2];
        state[0] = nums[0];
        state[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < length; i++) {
            int temp = state[1];
            state[1] = Math.max(state[1], state[0]+nums[i]);
            state[0] = temp;
        }
        return state[1];
    }
}
